# ABC331 振り返り
- [大和証券プログラミングコンテスト2023（AtCoder Beginner Contest 331） - AtCoder](https://atcoder.jp/contests/abc331)
- 成績 ABCE 4完 (1257) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc331)
![[スクリーンショット 2023-12-03 17.01.32.png]]
ABC331 でした。
D を飛ばしての 4完でしたが今回は D が難しい問題だったこともあり、水色パフォーマンスでした。レートは 994 となり前回の負け分を取り戻しました。
今回は D と E の配点が同じだったため両方問題を眺めていけそうな方から解こうと思い、D はグリッドだったので嫌な予感がして E に先を手をつけたのが幸いしました。
とはいえ、こういう立ち振る舞いが良かっただけでパフォーマンスが良いというのは、まあなんというかラッキーみたいなところがあり本来的にはどっちから手をつけても両方解けるぐらいのパワーが欲しいところです。
- A (灰) ··· カレンダー処理の問題。ある特定の年月日から1日進んだら? 日めくり / 月めくりを考慮する
- B (灰) ··· 卵を6, 8, 12個買えてそれぞれ値段がある。$N$ 個以上買う時の最安は? 全探索もしくは DP。
- C (灰) ··· 累積和とバケットで解く。セグ木で殴っても良い
- D (水) ··· 二次元累積和で与えられたグリッドの黒マスの数を数えつつ、周期性を考慮して超拡大した場合の合計黒マス数を数える。むずい
- E (緑) ··· 貪欲法であることに気づけば、簡単。降順にソートし、禁止されてる組み合わせを除いて線形探索する
でした。
E を解いた時点で残り 60 分近くあったので D いけるかなと思いましたが、ダメでした。
その後 upsolve も試みたのですがどうもどこかバグらせていて、未だ AC できてません。これは本番でも解けるはずがないですね。二次元累積和は細かい境界条件周りでごちゃつきがちなので、一度集中的に整理しようと思います。
---
## [A - Tomorrow](https://atcoder.jp/contests/abc331/tasks/abc331_a)
カレンダー処理の問題。条件分岐を丁寧やればいいだけなのですが、緊張してるところにこういう問題くると結構怖いです。
頭が混乱して 6分ぐらいかかってしまいました 😅
人間の脳内スタックがいかに貧弱か、よくわかります。A でつまづいてる人は他にもちらほら... こわ
ドキドキしながら書いた実装はこちら。これはひどいw
```haskell
main :: IO ()
main = do
[mx, dx] <- getInts
[y, m, d] <- getInts
let d' = if d + 1 > dx then 1 else d + 1
m' = if d' == 1 then (if m + 1 > mx then 1 else m + 1) else m
y' = if d' == 1 && m' == 1 then y + 1 else y
putStrLn . unwords . map show $ [y', m', d']
```
----
## [B - Buy One Carton of Milk](https://atcoder.jp/contests/abc331/tasks/abc331_b)
全探索でやればいいのですが、ドキドキの A の直後ということもありパッと全探索の解法出てこない。
脳死で書けるコードの方がいいや、と思い耐えきれず DP しました 😇
まあでもおかげで、実装しながら気持ちを落ち着けることができました。
```haskell
main :: IO ()
main = do
[n, s, m, l] <- getInts
dp <- newArray @IOUArray (0, 2 * n) (maxBound :: Int)
writeArray dp 0 0
for_ [0 .. n] $ \i -> do
v <- readArray dp i
for_ [(6, s), (8, m), (12, l)] $ \(x, k) -> do
when (v /= maxBound) $ do
updateArray min dp (min n (i + x)) (v + k)
ans <- readArray dp n
print ans
```
全探索するならこんな感じですかね。やや丁寧すぎるか。
```haskell
main :: IO ()
main = do
[n, s, m, l] <- getInts
let ss = map (\i -> (i * 6, i * s)) [0 .. (n `div` 6) + 1]
ms = map (\i -> (i * 8, i * m)) [0 .. (n `div` 8) + 1]
ls = map (\i -> (i * 12, i * l)) [0 .. (n `div` 12) + 1]
print $ minimum [x + y + z | [(a, x), (b, y), (c, z)] <- combinations 3 (ss ++ ms ++ ls), a + b + c >= n]
```
----
## [C - Sum of Numbers Greater Than Me](https://atcoder.jp/contests/abc331/tasks/abc331_c)
数列が与えられるが、並び順にあまり意味がないときはソートしたりバケット作ったりするのは定石です。
$A_i$ が $10^6$ 程度なので、$A_i$ ごとに出現回数のバケットを作ることができます。
バケットがあれば、ある $A_i$ が出現した場合の $+ A_i$ の総和もわかるので累積和テーブルが作れます。
というわけで累積和を作り、クエリを処理する。
$A_i$ より大きい、ので $A_i + 1$ 以降の総和を調べれば良いですね。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let m = maximum as
let bucket = accumArray @UArray (+) (0 :: Int) (1, m) $ map (,1) as
xs = map (uncurry (*)) (assocs bucket)
s = listArray @UArray (1, m + 1) $ scanl' (+) 0 xs
result = map f as
where
f a = s ! (m + 1) - s ! (a + 1)
putStrLn . unwords . map show $ result
```
コンテスト後の感想戦をみていると「セグ木で殴った」という人もちらほら。
なるほど、クエリは区間和取得ですし事前の更新は一点更新で行けそうですね。
セグメント木を使った解法も実装してみました。
数列を見ていって $A_i$ が出てきたら、索引 $A_i$ に $+ A_i$ する。クエリは $A_i + 1$ から末尾まで取得、で OK ですね。
```haskell
main :: IO ()
main = do
_ <- getInt
as <- getInts
let m = maximum as
tree <- newTree (+) (0 :: Int) (m + 1)
for_ as $ \ai -> do
updateTree tree ai (+ ai)
result <- mapM (\ai -> foldTree tree (ai + 1) (m + 1)) as
putStrLn . unwords . map show $ result
```
一点更新区間和だし、より実装が軽量な BIT でも良いでしょう。
```haskell
main :: IO ()
main = do
_ <- getInt
as <- getInts
let m = maximum as
bit <- newBIT @IOUArray (1, m)
for_ as $ \ai -> do
incrementBIT bit ai ai
result <- mapM (\ai -> rangeSumBIT bit (ai + 1) (m + 1)) as
putStrLn . unwords . map show $ result
```
私もそろそろセグメント木や BIT の扱いに慣れて、こういう問題でさっと出せるようになりたいところです。
----
## [D - Tile Pattern](https://atcoder.jp/contests/abc331/tasks/abc331_d) (未完 🍊)
二次元累積和と、うまいことやって部分的なブロックとフルブロックの個数を数えて... みたいにすれば解けるところまではわかったんですが、実際のその「うまいことやって」のところがなかなかうまく構成できず時間切れでした。
解説見ながら upslove しようにも、どうも答えが合わずまだ AC できていません。
----
## [E - Set Meal](https://atcoder.jp/contests/abc331/tasks/abc331_e)
貪欲法。$N$ 種類の主菜と $M$ 種類の副菜がある AtCoder 食堂 ··· デジャヴ感。
それもそのはず ABC321 D - Set Menu が問題文だけは激似です。あまりに似ていたので「あれ、自分もしかして間違えて過去問解いてる?」と思ってちょっとドキっとしてしまいました。
ABC321 D の方は累積和と二分探索だったこともあり、こちらも最初、二分探索かなーと思って考えていたのですがこの問題にはペアにしては行けない主菜と副菜が設定されているため、二分探索しようにも単調性がうまく確保できません。
が、よく考えると
1. 最も価格の高い定食の価格を求めるのだから、$a$ で最大のもの $b$ で最大のものを組み合わせれば最大価格になる
2. ただし禁止のペアがあるから組み合わせたものが禁止ペアの場合は、その次を選ぶ
これでいいことに気づきます。
$a_i$ を固定して $a_i$ に対して最適な $b_i$ を見つけます。あらかじめ数列 $b$ をソートしておけば、禁止ペアがなければ、$b$ の先頭を見るだけです。
もしそれがが禁止ペアだったらその次をみる。このとき禁止ペアは最大でも $L \leq 10^5$ ですから、スキップする回数は高々 $L$ 回までです。
というわけでソートして貪欲に先頭から見ていけば良いだけでした。
```haskell
main :: IO ()
main = do
[n, m, l] <- getInts
as <- getInts
bs <- getInts
xs <- replicateM l getTuple
let s = Set.fromList xs
let bs' = sortOn (Down . fst) $ zip bs [1 :: Int ..]
result = map f (zip as [1 :: Int ..])
where
f (ai, i) = do
(b, _) <- find (\(bi, j) -> Set.notMember (i, j) s) bs'
return (ai + b)
print $ maximum $ catMaybes result
```
----
## 感想など
水色パフォーマンスは出せましたが、自分より上位をとっている人たちを見るときちんと D も通して 5完、という人が多かったです。明らかな実力差を感じます、水色になるには今回の D 問題のような問題をきちっと解き切る実装力が必要ですね。
また、二次元累積和出ると嫌だなーとなんとなく思っていたところにばっちり出てきまして、まだ身体化できてない分野がありました。ここの補習はしっかりやっておきます。
レート $1000$ が目前に近づいてきました。今年の残り ABC はおそらく 3 〜 4 回。うち 1 回が私用で出られないことが確定しているので、あと 2 〜 3 回です。なんとかその数回で レード 1000 の大台に載せて、気持ちよく今年を締めくくりたいところ。頑張ります。